package 中等.搜索.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * 你可以按 任何顺序 返回答案。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/combinations/
 */
public class 组合_77 {

    public static void main(String[] args) {

        组合_77 impl = new 组合_77();
        System.out.println(impl.combine(4, 2));

    }

    /**
     * 回溯+剪枝
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> lists = new ArrayList<>();

        dfs(new ArrayList<>(), 1, n, k, lists);

        return lists;
    }

    private void dfs(List<Integer> list, int curN, int n, int k, List<List<Integer>> lists) {
        // 已经选择的元素个数+剩下的所有的元素 < k , 那么永远不能达到 k 个元素
        if (list.size() + n - curN + 1 < k) return;
        if (list.size() == k) {
            lists.add(new ArrayList<>(list));
            return;
        }

        for (int i = curN; i <= n; i++) {
            list.add(i);

            dfs(list, i + 1, n, k, lists);

            list.remove(list.size() - 1);
        }
    }

}
